#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur = 0, des = -1, s = arr.size();
        // 找到最后一个数
        while(des<s)
        {
            if(arr[cur]) des++;
            else des+=2;

            if(des == s - 1) break;
            cur++;
        }
        // 处理边界情况
        if(des == s)
        {
            arr[s - 1]=0;
            des-=2;
            cur--;
        }
        // 从后向前复写
        while(cur>=0)
        {
            if(arr[cur]) arr[des--] = arr[cur--];
            else
            {
                arr[des--] = 0;
                arr[des--] = 0;
                cur--;
            }
        }
    }
};

int main()
{
	vector<int> arr;
	arr = {1,0,2,3,0,4,5,0};

	Solution s;
	s.duplicateZeros(arr);
	
	for(int e : arr)
	{
		cout << e << " ";
	}

	return 0;
}

